#include <iostream>
#include <list>
#include <stdlib.h>
#include <time.h>

#define SWAP_INT(a,b) {a = a ^ b; b = a ^ b; a = a ^ b;}

using namespace std;

void init_int_list(list<int> &data, int n)
{
    for (int i = 0; i < n; ++i)
        data.push_back(rand()%10);
}

void print_int_list(list<int> &data)
{
    list<int>::iterator it = data.begin();
    for (it = data.begin(); it != data.end(); ++it)
        cout << *it << " ";
    cout << endl;
}

bool check(list<int> &data, list<int> &data_backup)
{
    int sum = 0, sum2 = 0;
    list<int>::iterator it = data.begin();
    list<int>::iterator it2 = ++(data.begin());
    for (; it2 != data.end(); ++it, ++it2)
    {
        sum += *it;
        if (*it2 < *it)
            return false;
    }
    sum += *it;
    for (it = data_backup.begin(); it != data_backup.end(); ++it)
        sum2 += *it;
    if (sum != sum2)
        return false;
    return true;
}

void quick(list<int> &data, list<int>::iterator left, list<int>::iterator right)
{
    list<int>::iterator i = left;
    list<int>::iterator j = right;
    int median = *left;

    while (j != i)
    {
        while (j != i && *j >= median)
        {
            --j;
        }
        while (j != i && *i <= median)
        {
            ++i;
        }
        if (i != j)
        {
            SWAP_INT(*i, *j)
        }
    }
    *left = *i;
    *i = median;

    list<int>::iterator x = i;
    --x;
    if (left != i && left != x)
    {
        quick(data, left, x);
    }

    x = i;
    ++x;
    if (right != i && right != x)
    {
        quick(data, x, right);
    }
}

int main(void)
{
    // 目测一次排序结果
    list<int> a;
    srand(time(NULL));
    init_int_list(a, 12);

    print_int_list(a);
    quick(a, a.begin(), --(a.end()));
    print_int_list(a);


    // 多次验证排序结果是否正确
    for(int i = 0; i < 300; ++i)
    {
        list<int> data, data_backup;
        init_int_list(data, 12);
        data_backup.assign(data.begin(), data.end());
        quick(data, data.begin(), --(data.end()));
        if (!check(data, data_backup))
        {
            cout << "error:" << endl << "Original data:" << endl;
            print_int_list(data_backup);
            cout << "Sorted data:" << endl;
            print_int_list(data);
            return EXIT_FAILURE;
        }
    }
    cout << "check" << endl;

    return EXIT_SUCCESS;
}
